package com.azure.code.dfs.island;

/**
 * 岛屿的最大面积
 *  Max Area of Island
 * https://leetcode.cn/problems/max-area-of-island/
 * */
public class Island_695 {

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length,n=grid[0].length;
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1){
                    max = Math.max(max,dfs(grid,i,j));
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid,int i,int j) {
        int m = grid.length,n = grid[0].length;
        if(i<0||j<0||i>=m||j>=n||grid[i][j]==0){
            return 0;
        }
        grid[i][j] = 0;
        return dfs(grid,i-1,j)+dfs(grid,i+1,j)
                +dfs(grid,i,j-1)+dfs(grid,i,j+1)
                +1;
    }

    public static void main(String[] args) {
        int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,0,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,0,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};

        System.out.println(new Island_695().maxAreaOfIsland(grid));
    }
}
